using System;
using Microsoft.SPOT;

namespace codebase
{
    public class HuffmanTree
    {

        #region Private Variables

        private int[] tree2d;

        #endregion

        #region Public Methods

        public int decode(ref bool decoded, ref int result, ref int treepos, int bit)
        {
            int numcodes = tree2d.Length / 2;
            if (treepos >= numcodes)
                return 11; //error: you appeared outside the codetree
            result = tree2d[2 * treepos + bit];
            decoded = (result < numcodes);
            treepos = decoded ? 0 : result - numcodes;
            return 0;
        }

        public int makeFromLengths(ref int[] bitlen, int maxbitlen)
        {
            int numcodes = (int)(bitlen.Length), treepos = 0, nodefilled = 0;
            int[] tree1d = new int[numcodes];
            int[] blcount = new int[maxbitlen + 1];
            int[] nextcode = new int[maxbitlen + 1];
            int i, n, bit;

            for (i = 0; i < numcodes; i++)
                blcount[bitlen[i]]++; //count number of instances of each code length

            for (i = 1; i <= maxbitlen; i++)
                nextcode[i] = (nextcode[i - 1] + blcount[i - 1]) << 1;

            for (i = 0; i < numcodes; i++)
            {
                if (bitlen[i] != 0)
                    tree1d[i] = nextcode[bitlen[i]]++;
            } //generate all the codes

            tree2d = new int[numcodes * 2];
            for (i = 0; i < tree2d.Length; i++)
                tree2d[i] = 32767; //32767 here means the tree2d isn't filled there yet

            for (n = 0; n < numcodes; n++) //the codes
            {
                for (i = 0; i < bitlen[n]; i++) //the bits for this code
                {
                    bit = (tree1d[n] >> (bitlen[n] - i - 1)) & 1;
                    if (treepos > numcodes - 2)
                        return 55;
                    if (tree2d[2 * treepos + bit] == 32767) //not yet filled in
                    {
                        if (i + 1 == bitlen[n])
                        {
                            tree2d[2 * treepos + bit] = n;
                            treepos = 0;
                        } //last bit
                        else
                        {
                            tree2d[2 * treepos + bit] = ++nodefilled + numcodes; treepos = nodefilled;
                        } //addresses are encoded as values > numcodes
                    }
                    else treepos = tree2d[2 * treepos + bit] - numcodes; //subtract numcodes from address to get address value

                }
            }

            return 0;
        }

        #endregion

    }
}
